import pdb
class ListNode(object):
    """docstring for ListNode"""
    def __init__(self, x):
        super(ListNode, self).__init__()
        self.val = x
        self.next = None


class Solution(object):
    """docstring for Solution"""
    # @param head, a ListNode
    # @param x, an integer
    # @return a ListNode
    def partition(self, head, x):
        pre = None
        q = head
        s_pre = None
        s = head
        while q and q.val < x:
            pre = q
            q = q.next
            s_pre = s
            s = s.next
        while s:
            if s.val >= x:
                s_pre = s
                s = s.next
            else:
                temp = s
                s = s.next
                s_pre.next = s
                if pre is None:
                    pre = temp
                    pre.next = q
                    head = pre
                else:
                    temp.next = q
                    pre.next = temp
                    pre = temp
        return head


# @param lst, a list
# @return a linked list
def make_list(lst):
    head = ListNode(lst[0])
    p = head
    for i in range(len(lst))[1:]:
        p.next = ListNode(lst[i])
        p = p.next
    return head


# @param lst, a linked list
def print_list(lst):
    while lst:
        print lst.val,
        lst = lst.next
    print " "

l = [1, 4, 3, 2, 5, 2]
head = make_list(l)
print_list(head)
#pdb.set_trace()
ss = Solution()
head = ss.partition(head, 6)
print_list(head)
